{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #queue #array #ordered-set #sliding-window #monotonic-queue #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #队列 #数组 #有序集合 #滑动窗口 #单调队列 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestSubarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #绝对差不超过限制的最长连续子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> ，和一个表示限制的整数 <code>limit</code>，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 <code>limit</code><em> 。</em></p>\n",
    "\n",
    "<p>如果不存在满足条件的子数组，则返回 <code>0</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [8,2,4,7], limit = 4\n",
    "<strong>输出：</strong>2 \n",
    "<strong>解释：</strong>所有子数组如下：\n",
    "[8] 最大绝对差 |8-8| = 0 &lt;= 4.\n",
    "[8,2] 最大绝对差 |8-2| = 6 &gt; 4. \n",
    "[8,2,4] 最大绝对差 |8-2| = 6 &gt; 4.\n",
    "[8,2,4,7] 最大绝对差 |8-2| = 6 &gt; 4.\n",
    "[2] 最大绝对差 |2-2| = 0 &lt;= 4.\n",
    "[2,4] 最大绝对差 |2-4| = 2 &lt;= 4.\n",
    "[2,4,7] 最大绝对差 |2-7| = 5 &gt; 4.\n",
    "[4] 最大绝对差 |4-4| = 0 &lt;= 4.\n",
    "[4,7] 最大绝对差 |4-7| = 3 &lt;= 4.\n",
    "[7] 最大绝对差 |7-7| = 0 &lt;= 4. \n",
    "因此，满足题意的最长子数组的长度为 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [10,1,2,4,7,2], limit = 5\n",
    "<strong>输出：</strong>4 \n",
    "<strong>解释：</strong>满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 &lt;= 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [4,2,2,2,4,4,2,2], limit = 0\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10^9</code></li>\n",
    "\t<li><code>0 &lt;= limit &lt;= 10^9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit](https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit](https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[8,2,4,7]\\n4', '[10,1,2,4,7,2]\\n5', '[4,2,2,2,4,4,2,2]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        ans = l = 0\n",
    "        qmin, qmax = deque(), deque()\n",
    "        for r, rv in enumerate(nums):\n",
    "            while qmin and nums[qmin[-1]] >= rv:\n",
    "                qmin.pop()\n",
    "            qmin.append(r)\n",
    "            while qmax and nums[qmax[-1]] <= rv:\n",
    "                qmax.pop()\n",
    "            qmax.append(r)\n",
    "\n",
    "            while qmin and qmax and nums[qmax[0]] - nums[qmin[0]] > limit:\n",
    "                if l == qmin[0]: qmin.popleft()\n",
    "                if l == qmax[0]: qmax.popleft()\n",
    "                l += 1\n",
    "            ans = max(ans, r - l + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        maxq,minq = deque(),deque()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        l =0\n",
    "        for r,x in enumerate(nums):\n",
    "            while maxq and nums[maxq[-1]]<x:\n",
    "                maxq.pop()\n",
    "            while minq and nums[minq[-1]]>x:\n",
    "                minq.pop()\n",
    "            minq.append(r)\n",
    "            maxq.append(r)\n",
    "            while nums[maxq[0]] -nums[minq[0]]>limit:\n",
    "                if maxq[0]<=l:\n",
    "                    maxq.popleft()\n",
    "                if minq[0]<=l:\n",
    "                    minq.popleft()\n",
    "                l+=1\n",
    "            ans = max(ans,r-l+1)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        ret=left=0\n",
    "        n,minQ,maxQ=len(nums),deque(),deque()\n",
    "        for i in range(n):\n",
    "            while minQ and minQ[-1]>nums[i]:\n",
    "                minQ.pop()\n",
    "            while maxQ and maxQ[-1]<nums[i]:\n",
    "                maxQ.pop()\n",
    "            maxQ.append(nums[i])\n",
    "            minQ.append(nums[i])\n",
    "            while maxQ and minQ and maxQ[0]-minQ[0]>limit:\n",
    "                if maxQ[0]==nums[left]:\n",
    "                    maxQ.popleft()\n",
    "                if minQ[0]==nums[left]:\n",
    "                    minQ.popleft()\n",
    "                left+=1\n",
    "            ret=max(ret,i-left+1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        def push(r):\n",
    "            while max_queue and max_queue[-1]<r:\n",
    "                max_queue.pop()\n",
    "            max_queue.append(r)\n",
    "            while min_queue and min_queue[-1]>r:\n",
    "                min_queue.pop()\n",
    "            min_queue.append(r)\n",
    "        def pop(l):\n",
    "            if l==max_queue[0]:\n",
    "                max_queue.popleft()\n",
    "            if l==min_queue[0]:\n",
    "                min_queue.popleft()\n",
    "        \n",
    "        from collections import deque\n",
    "        max_queue=deque([nums[0]])\n",
    "        min_queue=deque([nums[0]])\n",
    "        \n",
    "    \n",
    "        res=1\n",
    "        n=len(nums)\n",
    "        r=1\n",
    "        for l in range(n-1):       \n",
    "            while r<n and max_queue[0]-min_queue[0]<=limit:            \n",
    "                push(nums[r])  \n",
    "                r+=1\n",
    "                                                                   \n",
    "            if max_queue[0]-min_queue[0]<=limit and r-l>res:            \n",
    "                res=r-l            \n",
    "            if max_queue[0]-min_queue[0]>limit and r-1-l>res:                   \n",
    "                res=r-1-l            \n",
    "            if r==n:\n",
    "                break\n",
    "                \n",
    "            pop(nums[l])                                                    \n",
    "        return res\n",
    "     \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        qmx, qmn = deque(), deque()\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        r = 0\n",
    "        while r < len(nums):\n",
    "            right = nums[r]\n",
    "            while qmx and qmx[-1] < right:\n",
    "                qmx.pop()\n",
    "            qmx.append(right)\n",
    "            while qmn and qmn[-1] > right:\n",
    "                qmn.pop()\n",
    "            qmn.append(right)\n",
    "            while qmx and qmn and qmx[0] - qmn[0] > limit:\n",
    "                if nums[left] == qmx[0]:\n",
    "                    qmx.popleft()\n",
    "                if nums[left] == qmn[0]:\n",
    "                    qmn.popleft() \n",
    "                left += 1\n",
    "            ans = max(ans, r - left + 1)\n",
    "            r += 1\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        ans = 1\n",
    "        q_max = []\n",
    "        q_min = []\n",
    "        l = 0\n",
    "        for r, x in enumerate(nums):\n",
    "            while q_max and nums[q_max[-1]] <= x:\n",
    "                q_max.pop()\n",
    "            while q_min and nums[q_min[-1]] >= x:\n",
    "                q_min.pop()\n",
    "            q_max.append(r)\n",
    "            q_min.append(r)\n",
    "            while abs(nums[q_max[0]] - nums[q_min[0]] > limit):\n",
    "                l += 1\n",
    "                if q_max[0] < l:\n",
    "                    q_max.pop(0)\n",
    "                if q_min[0] < l:\n",
    "                    q_min.pop(0)\n",
    "            ans = max(ans, r - l + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        # abs(x-y) <= limit\n",
    "        # 8 9 9 5 4\n",
    "        # 8 12 12 8 8 7\n",
    "        ans = res = 0\n",
    "        l1 = l2 = -1\n",
    "        q = deque()\n",
    "        a,b = deque(), deque()\n",
    "        for i,x in enumerate(nums):\n",
    "            while a and x > nums[a[-1]]:\n",
    "                a.pop()\n",
    "            while b and x < nums[b[-1]]:\n",
    "                b.pop()\n",
    "            a.append(i)\n",
    "            b.append(i)\n",
    "            while nums[a[0]] - x > limit:\n",
    "                l1 = max(l1, a.popleft())\n",
    "            while x - nums[b[0]] > limit:\n",
    "                l2 = max(l2, b.popleft())\n",
    "            # print(i+1-min(a[0], b[0]), l1, l2, i-max(l1, l2))\n",
    "            ans = max(ans, i-max(l1, l2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        \"\"\"\n",
    "             最大值 最小值 不超过 t\n",
    "        \"\"\"\n",
    "        s = SortedList()\n",
    "        n =len(nums)\n",
    "        l= r= ret =0\n",
    "        while r < n:\n",
    "            s.add(nums[r])\n",
    "            while s[-1]-s[0]>limit:\n",
    "                s.remove(nums[l])\n",
    "                l+=1\n",
    "            ret = max(ret,r-l+1)\n",
    "            r+=1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        ans = 0\n",
    "        left = right = 0\n",
    "        slist = SortedList()\n",
    "        while right < len(nums):\n",
    "            slist.add(nums[right])\n",
    "            while slist[-1] - slist[0] > limit:\n",
    "                slist.remove(nums[left])\n",
    "                left += 1\n",
    "            ans = max(ans, len(slist))\n",
    "            right += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        s = SortedList()\n",
    "        left, right = 0, 0\n",
    "        res = 0\n",
    "\n",
    "        while right < len(nums):\n",
    "            s.add(nums[right])\n",
    "            while s[-1] - s[0] > limit:\n",
    "                s.remove(nums[left])\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "            right += 1\n",
    "\n",
    "        return res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        minq = [0]*100000\n",
    "        maxq = [0]*100000\n",
    "        maxn = 0\n",
    "        l = 0\n",
    "        maxh, maxt = 0, 0\n",
    "        minh, mint = 0, 0\n",
    "        for r in range(len(nums)):\n",
    "            while maxt > maxh and nums[r] >= nums[maxq[maxt-1]]:\n",
    "                maxt -= 1\n",
    "            maxq[maxt] = r\n",
    "            maxt += 1\n",
    "            while mint > minh and nums[r] <= nums[minq[mint-1]]:\n",
    "                mint -= 1\n",
    "            minq[mint] = r\n",
    "            mint += 1\n",
    "            while nums[maxq[maxh]]-nums[minq[minh]] > limit:\n",
    "                l += 1\n",
    "                if l > maxq[maxh]:\n",
    "                    maxh += 1\n",
    "                if l > minq[minh]:\n",
    "                    minh += 1\n",
    "            maxn = max(maxn, r-l+1)\n",
    "        return maxn\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        max_heap = list()\n",
    "        min_heap = list()\n",
    "        l, r = 0, 0\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        max_del = {}\n",
    "        min_del = {}\n",
    "        heapq.heappush(max_heap, -nums[r])\n",
    "        heapq.heappush(min_heap, nums[r])\n",
    "        while r < n:\n",
    "            while max_heap and -max_heap[0] in max_del:\n",
    "                t = -max_heap[0]\n",
    "                max_del[t] -= 1\n",
    "                if max_del[t] == 0:\n",
    "                    max_del.pop(t)\n",
    "                heapq.heappop(max_heap)\n",
    "            while min_heap and min_heap[0] in min_del:\n",
    "                t = min_heap[0]\n",
    "                min_del[t] -= 1\n",
    "                if min_del[t] == 0:\n",
    "                    min_del.pop(t)\n",
    "                heapq.heappop(min_heap)\n",
    "            if abs(-max_heap[0] - min_heap[0]) <= limit:\n",
    "                ans = max(ans, r - l + 1)\n",
    "                r += 1\n",
    "                if r >= n:\n",
    "                    break\n",
    "                heapq.heappush(max_heap, -nums[r])\n",
    "                heapq.heappush(min_heap, nums[r])\n",
    "            else:\n",
    "                if nums[l] not in max_del:\n",
    "                    max_del[nums[l]] = 0\n",
    "                max_del[nums[l]] += 1\n",
    "                if nums[l] not in min_del:\n",
    "                    min_del[nums[l]] = 0\n",
    "                min_del[nums[l]] += 1 \n",
    "                l += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        if max(set(nums)) - min(set(nums)) <= limit:\n",
    "            return len(nums)\n",
    "        res = 0\n",
    "        start = 0\n",
    "        s = []\n",
    "        for end in range(1, len(nums) + 1):\n",
    "            bisect.insort_left(s, nums[end-1])\n",
    "            while s[-1] - s[0] > limit:\n",
    "                s.pop(bisect.bisect_left(s, nums[start]))\n",
    "                res = max(res, end - start - 1)\n",
    "                start += 1\n",
    "            res = max(res, end - start)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        len_nums = len(nums)\n",
    "        longest_len = 1\n",
    "   \n",
    "        lb_lst = [num-limit for num in nums]\n",
    "        ub_lst = [num+limit for num in nums]\n",
    "        # print(list(zip(lb_lst,ub_lst)))\n",
    "\n",
    "        end_of_subarray = 1\n",
    "        for i in range(len_nums):\n",
    "        \n",
    "            # 初始化下界和上界\n",
    "            if (i == end_of_subarray):\n",
    "                lb = lb_lst[i]\n",
    "                ub = ub_lst[i]\n",
    "            else:\n",
    "                lb = max(lb_lst[i:end_of_subarray])\n",
    "                ub = min(ub_lst[i:end_of_subarray])\n",
    "\n",
    "            for j in range(end_of_subarray,len_nums):\n",
    "                end_of_subarray = len_nums\n",
    "                # if(i==1):\n",
    "                #     print('lb,ub: ',lb,ub)\n",
    "                if nums[j]<lb or nums[j]>ub:\n",
    "                    end_of_subarray = j\n",
    "                    break\n",
    "                lb = max(lb,lb_lst[j])\n",
    "                ub = min(ub,ub_lst[j])\n",
    "        \n",
    "            # print(i,end_of_subarray)\n",
    "            longest_len = max(longest_len,end_of_subarray-i)\n",
    "\n",
    "            if (len_nums-i)<longest_len:\n",
    "                break\n",
    "\n",
    "        return longest_len        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        i=0\n",
    "        j=1\n",
    "        \n",
    "        tmpmax=nums[0]\n",
    "        tmpmin=nums[0]\n",
    "        l=1\n",
    "        res=1\n",
    "        arr=[nums[i]]\n",
    "        dic=defaultdict(int)\n",
    "        dic[nums[0]]+=1\n",
    "        \n",
    "        while j<len(nums):\n",
    "            arr.append(nums[j])\n",
    "            \n",
    "            tmpmax=max(tmpmax,nums[j])\n",
    "            tmpmin=min(tmpmin,nums[j])\n",
    "            dic[nums[j]]+=1\n",
    "            \n",
    "            j+=1\n",
    "        \n",
    "            l+=1\n",
    "            \n",
    "            if abs(tmpmax-tmpmin)<=limit:\n",
    "                res=max(res,l)\n",
    "                #print(1,i,j)\n",
    "            else:\n",
    "                while abs(tmpmax-tmpmin)>limit:\n",
    "                    #print(2,i,j)\n",
    "                    \n",
    "                    dic[nums[i]]-=1\n",
    "                    \n",
    "                    if nums[i]==tmpmax and dic[nums[i]]==0:\n",
    "                        tmpmax=max(arr[1:])\n",
    "                    if nums[i]==tmpmin and dic[nums[i]]==0:\n",
    "                        tmpmin=min(arr[1:])\n",
    "                        \n",
    "                    i+=1\n",
    "                    del arr[0]\n",
    "                    l-=1\n",
    "                    \n",
    "        return res\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums, limit: int) -> int:\n",
    "        import heapq\n",
    "        res, iFirst = 0, 0\n",
    "        iLow, iHigh = {}, {}\n",
    "        nLow, nHigh = [], []\n",
    "        for i, a in enumerate(nums) :\n",
    "            if iLow.get(a, -1) < 0 :\n",
    "                heapq.heappush(nLow, a)\n",
    "            iLow[a] = i\n",
    "            if iHigh.get(a, -1) < 0 :\n",
    "                heapq.heappush(nHigh, -a)\n",
    "            iHigh[a] = i\n",
    "\n",
    "            if -nHigh[0] - nLow[0] > limit :\n",
    "                while iHigh[-nHigh[0]] < iFirst or -nHigh[0] - a > limit :\n",
    "                    j = iHigh.pop(-nHigh[0])\n",
    "                    if j >= iFirst : iFirst = j + 1                \n",
    "                    heapq.heappop(nHigh)\n",
    "                while iLow[nLow[0]] < iFirst or a - nLow[0] > limit :\n",
    "                    j = iLow.pop(nLow[0])\n",
    "                    if j >= iFirst : iFirst = j + 1\n",
    "                    heapq.heappop(nLow)\n",
    "            res = max(res, i-iFirst+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mint = 0\n",
    "minh = 0\n",
    "maxt = 0\n",
    "maxh = 0\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        def ok(limit, n):\n",
    "            global mint, minh, maxt, maxh\n",
    "            if mint <= minh:\n",
    "                min1 = n\n",
    "            else:\n",
    "                min1 = min(nums[minde[minh]], n)\n",
    "            if maxt <= maxh:\n",
    "                max1 = n\n",
    "            else:\n",
    "                max1 = max(nums[maxde[maxh]], n)\n",
    "            return (max1 - min1) <= limit\n",
    "        def push(r):\n",
    "            global mint, minh, maxt, maxh\n",
    "            while maxh < maxt and nums[maxde[maxt-1]] <= nums[r]:\n",
    "                maxt -= 1\n",
    "            maxde[maxt] = r\n",
    "            maxt += 1\n",
    "            while minh < mint and nums[minde[mint-1]] >= nums[r]:\n",
    "                mint -= 1\n",
    "            minde[mint] = r\n",
    "            mint += 1\n",
    "        def pop(l):\n",
    "            global mint, minh, maxt, maxh\n",
    "            if minh < mint and l == minde[minh]:\n",
    "                minh += 1\n",
    "            if maxh < maxt and l == maxde[maxh]:\n",
    "                maxh += 1\n",
    "        minde = [0 for _ in range(10**5 + 20000)]\n",
    "        maxde = [0 for _ in range(10**5 + 20000)]\n",
    "        l = 0\n",
    "        r = 0\n",
    "        ans = 0\n",
    "        while l < len(nums):\n",
    "            while r < len(nums) and ok(limit, nums[r]):\n",
    "                push(r)\n",
    "                r += 1\n",
    "            ans = max(ans, r - l)\n",
    "            pop(l)\n",
    "            l += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def check(nums, l, limit):\n",
    "    n = len(nums)\n",
    "    \n",
    "    q = [0] * (n + 1)\n",
    "    head = 1\n",
    "    tail = 0\n",
    "    min_queue = []\n",
    "    for i in range(n):\n",
    "        while head <= tail and q[head] <= i - l:\n",
    "            head += 1\n",
    "        while head <= tail and nums[q[tail]] >= nums[i]:\n",
    "            tail -= 1\n",
    "        tail += 1\n",
    "        q[tail] = i\n",
    "        if i >= l - 1:\n",
    "            min_queue.append(q[head])\n",
    "    q = [0] * (n + 1)\n",
    "    head = 1\n",
    "    tail = 0\n",
    "    max_queue = []\n",
    "    for i in range(n):\n",
    "        while head <= tail and q[head] <= i - l:\n",
    "            head += 1\n",
    "        while head <= tail and nums[q[tail]] <= nums[i]:\n",
    "            tail -= 1\n",
    "        tail += 1\n",
    "        q[tail] = i\n",
    "        if i >= l - 1:\n",
    "            max_queue.append(q[head])\n",
    "    # print(max_queue, min_queue, l)\n",
    "    if min([nums[max_queue[i]] - nums[min_queue[i]] for i in range(len(max_queue))]) > limit:\n",
    "        return False\n",
    "    return True\n",
    "    # max_val = max(nums[i: i + l])\n",
    "    # min_val = min(nums[i: i + l])\n",
    "    # for i in range(len(nums) - l + 1):\n",
    "    #     max_val = max(nums[i: i + l])\n",
    "    #     min_val = min(nums[i: i + l])\n",
    "    #     if max_val - min_val <= limit:\n",
    "    #         return True\n",
    "    # return False\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        n = len(nums)\n",
    "        left = 1\n",
    "        right = n\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            # print(left, right, mid)\n",
    "            if check(nums, mid, limit):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        if check(nums, left, limit):\n",
    "            return left\n",
    "        else:\n",
    "            return left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        ans, n = 1, len(nums)\n",
    "        q = deque()\n",
    "        index = -1\n",
    "        for i, num in enumerate(nums):\n",
    "            while q and (q[0][1] < index or abs(num - q[0][0]) > limit):\n",
    "                index = max(index, q.popleft()[1])\n",
    "            while q and (q[-1][1] < index or abs(num - q[-1][0]) > limit):\n",
    "                index = max(index, q.pop()[1])\n",
    "            bisect.insort_left(q, (num, i))\n",
    "            ans = max(ans, i - index)\n",
    "        return max(ans, n - index - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "min_queue, max_queue = deque(), deque()\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "\n",
    "        if not nums:\n",
    "            return 0\n",
    "\n",
    "        left, right, ans = 0, 0, 0\n",
    "        min_queue.clear()\n",
    "        max_queue.clear()\n",
    "        while right < len(nums):\n",
    "            right += 1\n",
    "            while min_queue and nums[min_queue[-1]] > nums[right - 1]:\n",
    "                min_queue.pop()\n",
    "            min_queue.append(right - 1)\n",
    "            while max_queue and nums[max_queue[-1]] < nums[right - 1]:\n",
    "                max_queue.pop()\n",
    "            max_queue.append(right - 1)\n",
    "\n",
    "            _min, _max = nums[min_queue[0]], nums[max_queue[0]]\n",
    "            while _max - _min > limit and left < right:\n",
    "                if min_queue[0] == left:\n",
    "                    min_queue.popleft()\n",
    "                if max_queue[0] == left:\n",
    "                    max_queue.popleft()\n",
    "                _min, _max = nums[min_queue[0]], nums[max_queue[0]]\n",
    "                left += 1\n",
    "            if right - left > ans:\n",
    "                ans = right - left\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        import heapq as hq\n",
    "        from collections import defaultdict\n",
    "\n",
    "        window_max_heap = []\n",
    "        window_min_heap = []\n",
    "        window_cnt = defaultdict(int)\n",
    "\n",
    "        start, res = 0, 0\n",
    "        for end in range(len(nums)):\n",
    "\n",
    "            window_cnt[nums[end]] += 1\n",
    "            hq.heappush(window_max_heap, -nums[end])\n",
    "            hq.heappush(window_min_heap, nums[end])\n",
    "\n",
    "            # if doesn't satisfy the limit condition\n",
    "            while window_max_heap and window_min_heap and abs(abs(window_max_heap[0])-window_min_heap[0]) > limit:\n",
    "                window_cnt[nums[start]] -= 1\n",
    "                # needs to clean the discared ele in heaps\n",
    "                while window_max_heap and window_cnt[abs(window_max_heap[0])] == 0:\n",
    "                    hq.heappop(window_max_heap)\n",
    "                while window_min_heap and window_cnt[abs(window_min_heap[0])] == 0:\n",
    "                    hq.heappop(window_min_heap)\n",
    "\n",
    "                start += 1\n",
    "            \n",
    "            res = max(res, end-start+1)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        #  time: O(nlogn)\n",
    "        # space: O(n)\n",
    "        \n",
    "        f = {}                      # sliding window 内部数字频次统计\n",
    "        qmx, qmn = [], []           # sliding window 内部数字的最大堆，最小堆\n",
    "        dmx, dmn = {}, {}           # lazy update 所需字典，用于保存从 window 左侧移出数字频次统计\n",
    "        res, i = 0, 0\n",
    "        for j, num in enumerate(nums):\n",
    "            f[num] = f.get(num, 0) + 1\n",
    "            heapq.heappush(qmx, -num)\n",
    "            heapq.heappush(qmn,  num)\n",
    "            while -qmx[0] - qmn[0] > limit:\n",
    "                f[nums[i]] -= 1\n",
    "                if not f[nums[i]]:\n",
    "                    del f[nums[i]]\n",
    "                dmx[nums[i]] = dmx.get(nums[i], 0) + 1\n",
    "                dmn[nums[i]] = dmn.get(nums[i], 0) + 1\n",
    "                i += 1\n",
    "                while -qmx[0] in dmx:\n",
    "                    v = -heapq.heappop(qmx)\n",
    "                    dmx[v] -= 1\n",
    "                    if not dmx[v]:\n",
    "                        del dmx[v]\n",
    "                while  qmn[0] in dmn:\n",
    "                    v =  heapq.heappop(qmn)\n",
    "                    dmn[v] -= 1\n",
    "                    if not dmn[v]:\n",
    "                        del dmn[v]\n",
    "            res = max(res, j - i + 1)\n",
    "        return res\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        min_heap, max_heap = list(), list()\n",
    "        counter = Counter()\n",
    "        ret = 0\n",
    "        l = 0\n",
    "        for r, n in enumerate(nums):\n",
    "            counter[n] += 1\n",
    "            heapq.heappush(min_heap, n)\n",
    "            heapq.heappush(max_heap, -n)\n",
    "            while l < r and -max_heap[0]-min_heap[0] > limit:\n",
    "                counter[nums[l]] -= 1\n",
    "                while counter[min_heap[0]] == 0:\n",
    "                    heapq.heappop(min_heap)\n",
    "                while counter[-max_heap[0]] == 0:\n",
    "                    heapq.heappop(max_heap)\n",
    "                l += 1\n",
    "            ret = max(r-l+1, ret)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... 460 ms ... 50 % ... 27.5 MB ... 9 %\n",
    "        #  time: O(nlogn)\n",
    "        # space: O(n)\n",
    "        \n",
    "        f = {}                      # sliding window 内部数字频次统计\n",
    "        qmx, qmn = [], []           # sliding window 内部数字的最大堆，最小堆\n",
    "        dmx, dmn = {}, {}           # lazy update 所需字典，用于保存从 window 左侧移出数字频次统计\n",
    "        res, i = 0, 0\n",
    "        for j, num in enumerate(nums):\n",
    "            f[num] = f.get(num, 0) + 1\n",
    "            heapq.heappush(qmx, -num)\n",
    "            heapq.heappush(qmn,  num)\n",
    "            while -qmx[0] - qmn[0] > limit:\n",
    "                f[nums[i]] -= 1\n",
    "                if not f[nums[i]]:\n",
    "                    del f[nums[i]]\n",
    "                dmx[nums[i]] = dmx.get(nums[i], 0) + 1\n",
    "                dmn[nums[i]] = dmn.get(nums[i], 0) + 1\n",
    "                i += 1\n",
    "                while -qmx[0] in dmx:\n",
    "                    v = -heapq.heappop(qmx)\n",
    "                    dmx[v] -= 1\n",
    "                    if not dmx[v]:\n",
    "                        del dmx[v]\n",
    "                while  qmn[0] in dmn:\n",
    "                    v =  heapq.heappop(qmn)\n",
    "                    dmn[v] -= 1\n",
    "                    if not dmn[v]:\n",
    "                        del dmn[v]\n",
    "            res = max(res, j - i + 1)\n",
    "        return res\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        l,r = 0,1\n",
    "        \n",
    "        from sortedcontainers import SortedList\n",
    "        sl = SortedList()\n",
    "        sl.add(nums[0])\n",
    "        cnt = Counter()\n",
    "        cnt[nums[0]] += 1\n",
    "        \n",
    "        res = 1\n",
    "        n = len(nums)\n",
    "        while r < n:\n",
    "            cnt[nums[r]] += 1\n",
    "            sl.add(nums[r])\n",
    "            \n",
    "            while sl[-1] - sl[0] > limit:\n",
    "                cnt[nums[l]] -= 1\n",
    "                while cnt[sl[0]] == 0:\n",
    "                    del sl[0]\n",
    "                \n",
    "                while cnt[sl[-1]] == 0:\n",
    "                    del sl[-1]\n",
    "                l += 1\n",
    "                \n",
    "            res = max(res,r-l+1)\n",
    "            r += 1\n",
    "        \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush, heappop\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        dic = defaultdict(int)\n",
    "        min_heap, max_heap = [], []\n",
    "        i, j = 0, 0\n",
    "        length = len(nums)\n",
    "        res = 0\n",
    "        while j < length:\n",
    "            heappush(max_heap, -nums[j])\n",
    "            heappush(min_heap, nums[j])\n",
    "            dic[nums[j]] += 1\n",
    "            while -max_heap[0] - min_heap[0] > limit:\n",
    "                dic[nums[i]] -= 1\n",
    "                while dic[-max_heap[0]] == 0:\n",
    "                    heappop(max_heap)\n",
    "                while dic[min_heap[0]] == 0:\n",
    "                    heappop(min_heap)\n",
    "                i += 1\n",
    "            res = max(res, j - i + 1)\n",
    "            j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        left, right,res = 0, 1, 0\n",
    "        # 用一个堆来维护已经遍历数组的顺序，元素是[值，索引]\n",
    "        heap = [[nums[0], 0]]\n",
    "        # 添加一个元素省略边界判定\n",
    "        nums.append(10**10 + 1)\n",
    "        while right < len(nums):\n",
    "            \n",
    "            if abs(nums[right] - heap[0][0]) > limit:\n",
    "                res = max(res, right - left)\n",
    "\n",
    "                # 按从小到大的顺序找到下一个在绝对范围的数据，及其位置\n",
    "                while heap and abs(nums[right] - heap[0][0]) > limit:\n",
    "                    heap.remove([nums[left], left])\n",
    "                    left += 1\n",
    "\n",
    "            elif abs(nums[right] - heap[-1][0]) > limit:\n",
    "                res = max(res, right - left)\n",
    "                while heap and abs(nums[right] - heap[-1][0]) > limit:\n",
    "                    heap.remove([nums[left], left])\n",
    "                    left += 1\n",
    "                    \n",
    "\n",
    "            \n",
    "            bisect.insort_right(heap, [nums[right], right])\n",
    "\n",
    "            right += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        n = len(nums)\n",
    "        window = collections.deque([[nums[0], 0]])\n",
    "        ans = 1\n",
    "        left = 0\n",
    "        for right in range(1, n):\n",
    "            if nums[right] < window[0][0]:\n",
    "                window.appendleft([nums[right], right])\n",
    "                max_value = nums[right] + limit\n",
    "                while window[-1][0] > max_value:\n",
    "                    left = window[-1][1] + 1\n",
    "                    window.pop()\n",
    "                    while window[-1][1] < left:\n",
    "                        window.pop()\n",
    "            elif nums[right] > window[-1][0]:\n",
    "                window.append([nums[right], right])\n",
    "                min_value = nums[right] - limit\n",
    "                while window[0][0] < min_value:\n",
    "                    left = window[0][1] + 1\n",
    "                    window.popleft()\n",
    "                    while window[0][1] < left:\n",
    "                        window.popleft()\n",
    "            else:\n",
    "                bisect.insort(window, [nums[right], right])\n",
    "            if n - left <= ans:\n",
    "                break\n",
    "            ans = max(ans, right - left + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        def check(nums, k, limit):\n",
    "            max_q, min_q = collections.deque(), collections.deque()\n",
    "            for i in range(len(nums)):\n",
    "                while min_q and nums[i] < nums[min_q[-1]]: min_q.pop()\n",
    "                while max_q and nums[i] > nums[max_q[-1]]: max_q.pop()\n",
    "                min_q.append(i)\n",
    "                max_q.append(i)\n",
    "                if i + 1 < k: continue\n",
    "                if i - max_q[0] == k: max_q.popleft()\n",
    "                if i - min_q[0] == k: min_q.popleft()\n",
    "                if nums[max_q[0]] - nums[min_q[0]] <= limit: return True\n",
    "            return False\n",
    "\n",
    "        def bs(l, r):\n",
    "            if l == r: return l\n",
    "            mid = (l + r + 1) >> 1\n",
    "            if check(nums, mid, limit):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "            return bs(l, r)\n",
    "        return bs(1, len(nums))\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: list[int], limit: int) -> int:\n",
    "        hh, lh = [], []\n",
    "        d = defaultdict(int)\n",
    "        p = 0\n",
    "        rst = 0\n",
    "        for q, n in enumerate(nums):\n",
    "            if not d[n]:\n",
    "                heapq.heappush(hh, -n)\n",
    "                heapq.heappush(lh, n)\n",
    "                \n",
    "            d[n] += 1\n",
    "            \n",
    "            while -hh[0] - lh[0] > limit:\n",
    "                d[nums[p]] -= 1\n",
    "                p += 1\n",
    "                while hh and not d[-hh[0]]:\n",
    "                    heapq.heappop(hh)\n",
    "                    \n",
    "                while lh and not d[lh[0]]:\n",
    "                    heapq.heappop(lh)\n",
    "            \n",
    "            rst = max(rst, q+1-p)\n",
    "        \n",
    "        return rst\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        window = SortedList()\n",
    "        ans = left = right = 0\n",
    "        while right < len(nums):\n",
    "            window.add((nums[right], right))\n",
    "            while left < right and abs(window[0][0] - window[-1][0]) > limit:\n",
    "                window.discard((nums[left], left))\n",
    "                left += 1\n",
    "            ans = max(ans, len(window))\n",
    "            right += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        left, right = 0, 0\n",
    "        m = {nums[left]: 1}\n",
    "        s_max = SortedList()\n",
    "        s_min = SortedList()\n",
    "        s_max.add(nums[left])\n",
    "        s_min.add(-nums[left])\n",
    "\n",
    "        while right < len(nums) - 1:\n",
    "            right += 1\n",
    "            if nums[right] in m:\n",
    "                m[nums[right]] += 1\n",
    "            else:\n",
    "                m[nums[right]] = 1\n",
    "\n",
    "            s_max.add(nums[right])\n",
    "            s_min.add(-nums[right])\n",
    "\n",
    "            max_top = s_max[len(s_max) - 1]\n",
    "\n",
    "            while m[max_top] <= 0:\n",
    "                s_max.pop()\n",
    "                max_top = s_max[len(s_max) - 1]\n",
    "\n",
    "            min_top = -s_min[len(s_min) - 1]\n",
    "            while m[min_top] <= 0:\n",
    "                s_min.pop()\n",
    "                min_top = -s_min[len(s_min) - 1]\n",
    "\n",
    "            if max_top - min_top <= limit:\n",
    "                continue\n",
    "            left += 1\n",
    "            m[nums[left - 1]] -= 1\n",
    "\n",
    "        return right - left + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums, limit: int) -> int:\n",
    "        count=collections.defaultdict(int)\n",
    "        maxheap=[]\n",
    "        minheap=[]\n",
    "        left=0\n",
    "        right=1\n",
    "        result=0\n",
    "        count[nums[0]]=1\n",
    "        heapq.heappush(maxheap,-nums[0])\n",
    "        heapq.heappush(minheap,nums[0])\n",
    "\n",
    "        while right<len(nums):\n",
    "            heapq.heappush(maxheap,-nums[right])\n",
    "            heapq.heappush(minheap,nums[right])\n",
    "            count[nums[right]]+=1\n",
    "\n",
    "            while maxheap and count[-maxheap[0]]==0:\n",
    "                heapq.heappop(maxheap)\n",
    "            while minheap and count[minheap[0]]==0:\n",
    "                heapq.heappop(minheap)\n",
    "\n",
    "            if abs(minheap[0]+maxheap[0])>limit:\n",
    "                count[nums[left]]-=1\n",
    "                left+=1\n",
    "            right+=1\n",
    "        return right-left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        st = SortedList()\n",
    "        n = len(nums)\n",
    "        left = right = 0\n",
    "        rst = 0\n",
    "        st.add((nums[right], right))\n",
    "        while right < n:\n",
    "            if st[-1][0] - st[0][0] > limit:\n",
    "                st.remove((nums[left], left))\n",
    "                left += 1\n",
    "            else:\n",
    "                rst = max(rst, right-left+1)\n",
    "                right += 1\n",
    "                if right < n:\n",
    "                    st.add((nums[right], right))\n",
    "        return rst\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        table = {}  # 记录每个数 最后一次 出现的位置\n",
    "        left = right = 0\n",
    "        x = y = 0  # max = nums[x], min = nums[y]\n",
    "        max_len = 1\n",
    "        for right in range(len(nums)):\n",
    "            table[nums[right]] = right\n",
    "            if nums[right] >= nums[x]:\n",
    "                x = right\n",
    "            if nums[right] <= nums[y]:\n",
    "                y = right\n",
    "            while nums[x] - nums[y] > limit:\n",
    "                max_len = max(max_len, right - left)\n",
    "                if x < y:\n",
    "                    left = x + 1\n",
    "                    x = table[sorted(nums[left:right + 1])[-1]]\n",
    "                else:\n",
    "                    left = y + 1\n",
    "                    y = table[sorted(nums[left:right + 1])[0]]\n",
    "        return max(max_len, right - left + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        # 子数组的最大值和最小值的差不能超过limit\n",
    "        # 懒删除堆 + 滑动窗口肯定是可以做的，但是代码会又长又臭\n",
    "        min_h = []\n",
    "        max_h = []\n",
    "        m = defaultdict(int)\n",
    "\n",
    "        left = maxlen = 0\n",
    "        for right, x in enumerate(nums):\n",
    "            m[x] += 1\n",
    "            heappush(min_h, x)\n",
    "            heappush(max_h, -x)\n",
    "            while - max_h[0] - min_h[0] > limit:\n",
    "                # 1、首先把左侧的数从字典中删除\n",
    "                m[nums[left]] -= 1\n",
    "                # 2、然后动态更新一下大小懒删除堆\n",
    "                while m[-max_h[0]] == 0:\n",
    "                    heappop(max_h)\n",
    "                while m[min_h[0]] == 0:\n",
    "                    heappop(min_h)\n",
    "                # 3、然后左侧指针动一下\n",
    "                left += 1\n",
    "\n",
    "            maxlen = max(maxlen, right-left+1)\n",
    "        \n",
    "        return maxlen\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        l,ans,min_nums,max_nums = 0,0,[],[]\n",
    "        dic = defaultdict(int)\n",
    "        for r,n in enumerate(nums):\n",
    "            dic[n] += 1\n",
    "            heapq.heappush(max_nums,-n)\n",
    "            heapq.heappush(min_nums,n)\n",
    "            while abs(-max_nums[0] - min_nums[0]) > limit:\n",
    "                dic[nums[l]] -= 1\n",
    "                while dic[-max_nums[0]] == 0:\n",
    "                    -heapq.heappop(max_nums)\n",
    "                while dic[min_nums[0]] == 0:\n",
    "                    heapq.heappop(min_nums)\n",
    "                if dic[nums[l]] == 0:\n",
    "                    del dic[nums[l]]\n",
    "                l += 1\n",
    "            ans = max(ans,r-l+1)\n",
    "            #print(nums[l:r+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        if len(nums) <= 1:\n",
    "            return len(nums)\n",
    "        local_max_window = deque()\n",
    "        local_min_window = deque()\n",
    "        local_min_window.append((0,nums[0]))\n",
    "        local_max_window.append((0,nums[0]))\n",
    "        p_l = 0\n",
    "        p_r = 1\n",
    "        result = 1\n",
    "        l = len(nums)\n",
    "        while p_r < l:\n",
    "            while ((not local_max_window) or (not local_min_window) or (local_max_window and local_min_window and local_max_window[0][1] - local_min_window[0][1] <= limit)) and p_r < l:\n",
    "                num_r = nums[p_r]\n",
    "                while local_max_window and local_max_window[-1][1] < num_r:\n",
    "                    local_max_window.pop()\n",
    "                local_max_window.append((p_r,num_r))\n",
    "                while local_min_window and local_min_window[-1][1] > num_r:\n",
    "                    local_min_window.pop()\n",
    "                local_min_window.append((p_r,num_r))\n",
    "                p_r += 1\n",
    "                if local_max_window[0][1] - local_min_window[0][1] <= limit:\n",
    "                    result = max(result, p_r - p_l)\n",
    "            while local_min_window and local_max_window and local_max_window[0][1] - local_min_window[0][1] > limit:\n",
    "                if local_max_window[0][0] == p_l:\n",
    "                    local_max_window.popleft()\n",
    "                if local_min_window[0][0] == p_l:\n",
    "                    local_min_window.popleft()\n",
    "                p_l += 1\n",
    "                result = max(result, p_r - p_l)        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class MMQueue:\n",
    "    def __init__(self):\n",
    "        self.miq = collections.deque()\n",
    "        self.maq = collections.deque()\n",
    "    \n",
    "    def enqueue(self, v):\n",
    "        c = 1\n",
    "        while self.miq and self.miq[-1][0] > v:\n",
    "            c += self.miq.pop()[1]\n",
    "        self.miq.append([v, c])\n",
    "        \n",
    "        c = 1\n",
    "        while self.maq and self.maq[-1][0] < v:\n",
    "            c += self.maq.pop()[1]\n",
    "        self.maq.append([v, c])\n",
    "    \n",
    "    def dequeue(self):\n",
    "        ami = self.min()\n",
    "        ama = self.max()\n",
    "        \n",
    "        self.miq[0][1] -= 1\n",
    "        if self.miq[0][1] <= 0: self.miq.popleft()\n",
    "        self.maq[0][1] -= 1\n",
    "        if self.maq[0][1] <= 0: self.maq.popleft()\n",
    "        \n",
    "        return ami, ama\n",
    "    \n",
    "    def min(self):\n",
    "        return self.miq[0][0] if self.miq else 0\n",
    "    def max(self):\n",
    "        return self.maq[0][0] if self.maq else 0\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def longestSubarray(self, A, limit):\n",
    "        mq = MMQueue()\n",
    "        ans = j = 0\n",
    "        N = len(A)\n",
    "        for i, x in enumerate(A):\n",
    "            while j < N and mq.max() - mq.min() <= limit:\n",
    "                ans = max(ans, j - i)\n",
    "                mq.enqueue(A[j]); j += 1\n",
    "            if mq.max() - mq.min() <= limit:\n",
    "                ans = max(ans, j - i)\n",
    "            mq.dequeue()\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        ind_start = 0\n",
    "        ind_end = 0\n",
    "        res = 1\n",
    "        max_queue = []\n",
    "        min_queue = []\n",
    "        remove_set_max = {}\n",
    "        remove_set_min = {}\n",
    "        while ind_end < len(nums):\n",
    "            heapq.heappush(max_queue, -nums[ind_end])\n",
    "            heapq.heappush(min_queue, nums[ind_end])\n",
    "            while -max_queue[0] - min_queue[0] > limit:\n",
    "                if nums[ind_start] not in remove_set_max:\n",
    "                    remove_set_max[nums[ind_start]] = 1\n",
    "                    remove_set_min[nums[ind_start]] = 1\n",
    "                else:\n",
    "                    remove_set_max[nums[ind_start]] += 1\n",
    "                    remove_set_min[nums[ind_start]] += 1\n",
    "                ind_start += 1\n",
    "                while (-max_queue[0]) in remove_set_max and remove_set_max[-max_queue[0]] > 0:\n",
    "                    remove_set_max[-max_queue[0]] -= 1\n",
    "                    heapq.heappop(max_queue)\n",
    "                while min_queue[0] in remove_set_min and remove_set_min[min_queue[0]] > 0:\n",
    "                    remove_set_min[min_queue[0]] -= 1\n",
    "                    heapq.heappop(min_queue)\n",
    "            ind_end += 1\n",
    "            res = max(res, ind_end-ind_start)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        # 栈底维护了最值，栈顶维护了窗口终点\n",
    "\n",
    "        ascend, descend = [], [] # 维护一个最小值栈，一个最大值栈\n",
    "        a, d = 0, 0 # 队首下标\n",
    "        t = 0 # 窗口起始点\n",
    "        res = 0\n",
    "\n",
    "        for i in range(len(nums)): # i为窗口终止点，利用循环滑动终止点\n",
    "            temp = nums[i] # 保存终止点对应的值\n",
    "\n",
    "            # 更新最小值\n",
    "            while len(ascend) > a and temp < ascend[-1][0]: # 与栈顶值对比\n",
    "                ascend.pop() # 弹出\n",
    "            ascend.append((temp, i)) # 记录终点值与下标\n",
    "            \n",
    "            # 更新最大值\n",
    "            while len(descend) > d and temp > descend[-1][0]: # 与栈顶值对比\n",
    "                descend.pop() # 弹出\n",
    "            descend.append((temp, i)) # 记录终点值与下标\n",
    "\n",
    "            while descend[d][0] - ascend[a][0] > limit: # 最值之差大于limit出发滑动条件\n",
    "                t += 1 # 起始点滑动\n",
    "                if ascend[a][1] < t: # 如果窗口起点在最小值索引右侧，需要舍弃此时的最小值\n",
    "                    a += 1\n",
    "                if descend[d][1] < t: # 如果窗口起点在最大值索引右侧，需要舍弃此时的最大值\n",
    "                    d += 1\n",
    "            \n",
    "            res = max(res, i-t+1) # 更新最大长度\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        from collections import deque\n",
    "        max_q = deque()\n",
    "        min_q = deque()\n",
    "        ans = 0\n",
    "        left = -1\n",
    "        for i, n in enumerate(nums):\n",
    "            while max_q and max_q[-1][1] < n:\n",
    "                max_q.pop()\n",
    "            max_q.append((i, n))\n",
    "            while min_q and min_q[-1][1] > n:\n",
    "                min_q.pop()\n",
    "            min_q.append((i, n))\n",
    "            cur_max = max_q[0][1]\n",
    "            cur_min = min_q[0][1]\n",
    "            while (cur_max - cur_min) > limit:\n",
    "                left += 1\n",
    "                while min_q and min_q[0][0] <= left:\n",
    "                    min_q.popleft()\n",
    "                while max_q and max_q[0][0] <= left:\n",
    "                    max_q.popleft()\n",
    "                cur_max = max_q[0][1]\n",
    "                cur_min = min_q[0][1]\n",
    "            ans = max(ans, i - left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        min_queue, max_queue = collections.deque(), collections.deque()\n",
    "        res = 0\n",
    "        start = 0  # 窗口左边界\n",
    "        for end, num in enumerate(nums):\n",
    "            while min_queue and num < min_queue[-1][0]:\n",
    "                min_queue.pop()\n",
    "            min_queue.append((num, end))\n",
    "            while max_queue and num > max_queue[-1][0]:\n",
    "                max_queue.pop()\n",
    "            max_queue.append((num, end))\n",
    "            while abs(max_queue[0][0] - min_queue[0][0]) > limit:\n",
    "                start += 1\n",
    "                if min_queue[0][1] < start:\n",
    "                    min_queue.popleft()\n",
    "                if max_queue[0][1] < start:\n",
    "                    max_queue.popleft()\n",
    "            res = max(res, end - start + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        from collections import deque\n",
    "        max_q = deque()\n",
    "        min_q = deque()\n",
    "        ans = 0\n",
    "        left = -1\n",
    "        for i, n in enumerate(nums):\n",
    "            while max_q and max_q[-1][1] < n:\n",
    "                max_q.pop()\n",
    "            max_q.append((i, n))\n",
    "            while min_q and min_q[-1][1] > n:\n",
    "                min_q.pop()\n",
    "            min_q.append((i, n))\n",
    "            cur_max = max_q[0][1]\n",
    "            cur_min = min_q[0][1]\n",
    "            while (cur_max - cur_min) > limit:\n",
    "                left += 1\n",
    "                while min_q and min_q[0][0] <= left:\n",
    "                    min_q.popleft()\n",
    "                while max_q and max_q[0][0] <= left:\n",
    "                    max_q.popleft()\n",
    "                cur_max = max_q[0][1]\n",
    "                cur_min = min_q[0][1]\n",
    "            ans = max(ans, i - left)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        qmax = deque()\n",
    "        qmin = deque()\n",
    "        l = 0\n",
    "        for r, x in enumerate(nums):\n",
    "            while qmax and qmax[-1][0] < x: qmax.pop()\n",
    "            while qmin and qmin[-1][0] > x: qmin.pop()\n",
    "            qmax.append((x, r))\n",
    "            qmin.append((x, r))\n",
    "            if qmax[0][0] - qmin[0][0] > limit:\n",
    "                l += 1\n",
    "                while qmax[0][1] < l: qmax.popleft()\n",
    "                while qmin[0][1] < l: qmin.popleft()\n",
    "        return len(nums) - l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        qmax = deque()\n",
    "        qmin = deque()\n",
    "        l = 0\n",
    "        for r, x in enumerate(nums):\n",
    "            while qmax and qmax[-1][0] < x: qmax.pop()\n",
    "            while qmin and qmin[-1][0] > x: qmin.pop()\n",
    "            qmax.append((x, r))\n",
    "            qmin.append((x, r))\n",
    "            if qmax[0][0] - qmin[0][0] > limit:\n",
    "                l += 1\n",
    "                while qmax[0][1] < l: qmax.popleft()\n",
    "                while qmin[0][1] < l: qmin.popleft()\n",
    "        return len(nums) - l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        n = len(nums)\n",
    "        res = 1\n",
    "        minq = deque()\n",
    "        maxq = deque()\n",
    "        l = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            while minq and minq[-1][0] > nums[i]:\n",
    "                minq.pop()\n",
    "            while maxq and maxq[-1][0] < nums[i]:\n",
    "                maxq.pop()\n",
    "            minq.append((nums[i], i))\n",
    "            maxq.append((nums[i], i))\n",
    "            if maxq[0][0] - minq[0][0] <= limit:\n",
    "                res = max(res, i - l + 1)\n",
    "            else:\n",
    "                while maxq[0][0] - minq[0][0] > limit:\n",
    "                    if maxq[0][1] > minq[0][1]:\n",
    "                        _, index = minq.popleft()\n",
    "                        l = max(l, index + 1)\n",
    "                    else:\n",
    "                        _, index = maxq.popleft()\n",
    "                        l = max(l, index + 1)\n",
    "                res = max(res, i - l + 1)\n",
    "\n",
    "        return res\n",
    "                \n",
    "                    \n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        maxq, minq = deque(), deque()\n",
    "        j, maxl = 0, 0\n",
    "        for i, num in enumerate(nums):\n",
    "            while maxq and num > maxq[-1][0]:\n",
    "                maxq.pop()\n",
    "            maxq.append((num, i))\n",
    "            while minq and num < minq[-1][0]:\n",
    "                minq.pop()\n",
    "            minq.append((num, i))\n",
    "            while maxq[0][0] - minq[0][0] > limit:\n",
    "                while maxq[0][1] <= j: maxq.popleft()\n",
    "                while minq[0][1] <= j: minq.popleft()\n",
    "                j += 1\n",
    "            maxl = max(maxl, i - j + 1) \n",
    "        return maxl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def  longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return n\n",
    "\n",
    "        queuemin= collections.deque()\n",
    "        queuemin.append((nums[0], 0))\n",
    "        queuemax = collections.deque()\n",
    "        queuemax.append((nums[0], 0))\n",
    "\n",
    "        maxlength = 1\n",
    "        start = 0\n",
    "        for i in range(1, n):\n",
    "            while queuemin and queuemin[-1][0] > nums[i]:\n",
    "                queuemin.pop()\n",
    "            queuemin.append((nums[i], i))\n",
    "            while queuemax and queuemax[-1][0] < nums[i]:\n",
    "                queuemax.pop()\n",
    "            queuemax.append((nums[i], i))\n",
    "            if queuemax[0][0] - queuemin[0][0] > limit:\n",
    "                maxlength = max(maxlength, i - start)\n",
    "                if queuemin[0][1] == i:\n",
    "                    while queuemax[0][0] - nums[i] > limit:\n",
    "                        res = queuemax.popleft()\n",
    "                    start = res[1] + 1\n",
    "                elif queuemax[0][1] == i:\n",
    "                    while nums[i] - queuemin[0][0] > limit:\n",
    "                        res = queuemin.popleft()\n",
    "                    start = res[1] + 1\n",
    "        maxlength = max(maxlength, n - start)\n",
    "        return maxlength"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "class Bit:\n",
    "    def lowbit(self, x):\n",
    "        return x & -x\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.bit = [-1] * n\n",
    "    \n",
    "    def update(self, j, x):\n",
    "        while j < self.n:\n",
    "            self.bit[j] = max(self.bit[j], x)\n",
    "            j += self.lowbit(j)\n",
    "    \n",
    "    def query(self, j):\n",
    "        l = -1\n",
    "        while j > 0:\n",
    "            l = max(l, self.bit[j])\n",
    "            j -= self.lowbit(j)\n",
    "        return l\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        if not nums: return 0\n",
    "        t = [-1e9] + sorted(set(nums))\n",
    "        d = {x: i for i, x in enumerate(t)}\n",
    "        n = len(nums) + 1\n",
    "        \n",
    "        lbit = Bit(n)\n",
    "        hbit = Bit(n)\n",
    "\n",
    "        left = [None] * len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            ilow = bisect.bisect_left(t, x - limit) - 1\n",
    "            prevlow = lbit.query(ilow)\n",
    "            ix = d[x]\n",
    "            prevhigh = hbit.query(len(t) - ix - 1)\n",
    "            # print(prevlow, prevhigh)\n",
    "            left[i] = i - max(prevlow, prevhigh)\n",
    "            lbit.update(ix, i)\n",
    "            hbit.update(len(t) - ix, i)\n",
    "        # print(left)\n",
    "        \n",
    "        ans = 0\n",
    "        lbit = Bit(n)\n",
    "        hbit = Bit(n)\n",
    "        for i, (x, l) in enumerate(zip(nums[::-1], left[::-1])):\n",
    "            ilow = bisect.bisect_left(t, x - limit) - 1\n",
    "            prevlow = lbit.query(ilow)\n",
    "            ix = d[x]\n",
    "            prevhigh = hbit.query(len(t) - ix - 1)\n",
    "            r = i - max(prevlow, prevhigh)\n",
    "            ans = max(ans, l + r - 1)\n",
    "            lbit.update(ix, i)\n",
    "            hbit.update(len(t) - ix, i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\r\n",
    "import heapq\r\n",
    "class Solution:\r\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\r\n",
    "        max_heap = []\r\n",
    "        min_heap = []\r\n",
    "        min_to_del = collections.Counter()\r\n",
    "        max_to_del = collections.Counter()\r\n",
    "        max_length = 0\r\n",
    "        left = right = 0\r\n",
    "        n = len(nums)\r\n",
    "        while right < n:\r\n",
    "            heapq.heappush(min_heap, nums[right])\r\n",
    "            heapq.heappush(max_heap, -nums[right])\r\n",
    "            while -max_heap[0] - min_heap[0] > limit:\r\n",
    "                min_to_del[nums[left]] += 1\r\n",
    "                max_to_del[nums[left]] += 1\r\n",
    "                while min_heap and min_to_del[min_heap[0]] > 0:\r\n",
    "                    min_to_del[min_heap[0]] -= 1\r\n",
    "                    heapq.heappop(min_heap)\r\n",
    "                while max_heap and max_to_del[-max_heap[0]] > 0:\r\n",
    "                    max_to_del[-max_heap[0]] -= 1\r\n",
    "                    heapq.heappop(max_heap)\r\n",
    "                left += 1\r\n",
    "            max_length = max(max_length, right - left + 1)\r\n",
    "            right += 1\r\n",
    "        return max_length\r\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        decrease=[]\n",
    "        increase=[]\n",
    "        d=0\n",
    "        i=0\n",
    "        t=0\n",
    "        res=0\n",
    "        for j in range(len(nums)):\n",
    "            while len(decrease)>d and decrease[-1][0]<nums[j]:\n",
    "                decrease.pop()\n",
    "            decrease.append((nums[j],j))\n",
    "            while len(increase)>i and increase[-1][0]>nums[j]:\n",
    "                increase.pop()\n",
    "            increase.append((nums[j],j))\n",
    "            while decrease[d][0]-increase[i][0]>limit:\n",
    "                t+=1\n",
    "                if increase[i][1]<t:\n",
    "                    i+=1\n",
    "                if decrease[d][1]<t:\n",
    "                    d+=1\n",
    "            res=max(res,j-t+1)\n",
    "        return res\n",
    "            \n",
    "\n",
    "        \n",
    "                       \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        minh = []\n",
    "        maxh = []\n",
    "        import heapq\n",
    "        l,r = 0,0\n",
    "        length = 0\n",
    "        while r<len(nums):\n",
    "            heapq.heappush(minh,(nums[r],r))\n",
    "            heapq.heappush(maxh,(-nums[r],r))\n",
    "            while minh and minh[0][1]<l:\n",
    "                heapq.heappop(minh)\n",
    "            mini,idx = minh[0]\n",
    "            while maxh and maxh[0][1]<l:\n",
    "                heapq.heappop(maxh)\n",
    "            maxi,idx1 = maxh[0]\n",
    "            if -maxi-mini>limit:\n",
    "                l = min(idx,idx1)+1\n",
    "            else:\n",
    "                length = max(r-l+1,length)\n",
    "            r+=1\n",
    "        return length\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "\n",
    "        import heapq\n",
    "        max_h = [(-nums[0], 0)]\n",
    "        min_h = [(nums[0], 0)]\n",
    "        st = -1\n",
    "        n = len(nums)\n",
    "        ans = 1\n",
    "\n",
    "        for ed in range(1, n):\n",
    "            \n",
    "            while max_h and ( (abs(-max_h[0][0] - nums[ed]) > limit)):\n",
    "                (_, loc) = heapq.heappop(max_h)\n",
    "                st = max(st, loc)\n",
    "\n",
    "            while min_h and ( (abs(min_h[0][0] - nums[ed]) > limit)):\n",
    "                (_, loc) = heapq.heappop(min_h)\n",
    "                st = max(st, loc)\n",
    "\n",
    "            ans = max(ans, ed-st)\n",
    "            heapq.heappush(max_h, (-nums[ed], ed))\n",
    "            heapq.heappush(min_h, (nums[ed], ed))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        aq = []  # 升序队列\n",
    "        bq = []  # 降序队列\n",
    "        at = 0\n",
    "        bt = 0\n",
    "        t = 0  # 窗口开始位置t\n",
    "        ret = 0\n",
    "        for i in range(len(nums)):  # 窗口结束位置i\n",
    "            x = nums[i]\n",
    "            while len(aq) > at and x < aq[-1][0]:\n",
    "                aq.pop()\n",
    "            aq.append((x, i))\n",
    "            while len(bq) > bt and x > bq[-1][0]:\n",
    "                bq.pop()\n",
    "            bq.append((x, i))\n",
    "            while bq[bt][0] - aq[at][0] > limit:\n",
    "                t += 1\n",
    "                if aq[at][1] < t:\n",
    "                    at += 1\n",
    "                if bq[bt][1] < t:\n",
    "                    bt += 1\n",
    "            if i - t + 1 > ret:\n",
    "                ret = i - t + 1\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        ans, n = 1, len(nums)\n",
    "        q_asc = []\n",
    "        q_desc = []\n",
    "        index = -1\n",
    "        for i, num in enumerate(nums):\n",
    "            while q_asc and (q_asc[0][1] < index or abs(num - q_asc[0][0]) > limit):\n",
    "                index = max(index, heapq.heappop(q_asc)[1])\n",
    "            heapq.heappush(q_asc, (num, i))\n",
    "            while q_desc and (q_desc[0][1] < index or abs(num + q_desc[0][0]) > limit):\n",
    "                index = max(index, heapq.heappop(q_desc)[1])\n",
    "            heapq.heappush(q_desc, (-num, i))\n",
    "            ans = max(ans, i - index)\n",
    "        return max(ans, n - index - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        l,r=0,1\n",
    "        h1,h2=[(nums[0],0)],[(-nums[0],0)]\n",
    "        n=len(nums)\n",
    "        \n",
    "        ans=1\n",
    "        while True:\n",
    "            # print(l,r)\n",
    "            diff=abs(h2[0][0]+h1[0][0])\n",
    "            # print(diff)\n",
    "            if diff<=limit:\n",
    "                ans=max(ans,r-l)\n",
    "                if r==n: break\n",
    "                else:\n",
    "                    heappush(h1, (nums[r],r))\n",
    "                    heappush(h2, (-nums[r],r))\n",
    "                    r+=1\n",
    "            else:\n",
    "                l+=1\n",
    "                while h1 and h1[0][1]<l:\n",
    "                    heappop(h1)\n",
    "                while h2 and h2[0][1]<l:\n",
    "                    heappop(h2)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        l = 0; ans = 1\n",
    "        mx, mn = [], []\n",
    "        def popOutdated():\n",
    "            while mx and mx[0][1]<l: heappop(mx)\n",
    "            while mn and mn[0][1]<l: heappop(mn)\n",
    "        for r, num in enumerate(nums):\n",
    "            heappush(mn, (num, r)); heappush(mx, (-num, r))\n",
    "            popOutdated()\n",
    "            while -mx[0][0]-mn[0][0]>limit:\n",
    "                l += 1\n",
    "                popOutdated()\n",
    "            ans = max(ans, r-l+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        import heapq\n",
    "        n, p1, p2, h1, h2, output = len(nums), 0, 1, [(nums[0],0)], [(-nums[0],0)], 1\n",
    "        while p2<n:\n",
    "            heapq.heappush(h1, (nums[p2],p2))\n",
    "            heapq.heappush(h2, (-nums[p2],p2))\n",
    "            tmp = heapq.heappop(h1)\n",
    "            while nums[p2]-tmp[0] > limit:\n",
    "                if tmp[1]>=p1:\n",
    "                    p1 = tmp[1]+1\n",
    "                tmp = heapq.heappop(h1)\n",
    "            heapq.heappush(h1, tmp)\n",
    "            tmp = heapq.heappop(h2)\n",
    "            while -tmp[0]-nums[p2] > limit:\n",
    "                if tmp[1]>=p1:\n",
    "                    p1 = tmp[1]+1\n",
    "                tmp = heapq.heappop(h2)\n",
    "            heapq.heappush(h2, tmp)\n",
    "            output = max(output, p2-p1+1)\n",
    "            p2 = p2+1\n",
    "        return output\n",
    "        \"\"\"\n",
    "        n, p1, p2, d, low, high, output = len(nums), 0, 1, collections.OrderedDict([]), nums[0], nums[0], 1\n",
    "        d[nums[0]]=0\n",
    "        while p2<n:\n",
    "            d[nums[p2]]= p2 \n",
    "            if nums[p2]-low > limit:\n",
    "                tmp = d.popitem(last=True)\n",
    "                print(p2, tmp, d )\n",
    "                indices = [tmp[1]]\n",
    "                while nums[p2]-tmp[0]>limit:\n",
    "                    tmp = d.popitem(last=True)\n",
    "                    indices.append(tmp[1])\n",
    "                indices.pop()\n",
    "                low, p1 = tmp[0], indices[-1]+1\n",
    "                d[tmp[0]] = tmp[1]\n",
    "            if high-nums[p2] > limit:\n",
    "                tmp = d.popitem(last=False)\n",
    "                print(p2, tmp, d )\n",
    "                indices = [tmp[1]]\n",
    "                while tmp[0]-nums[p2]>limit:\n",
    "                    tmp = d.popitem(last=False)\n",
    "                    indices.append(tmp[1])\n",
    "                indices.pop()\n",
    "                high, p1 = tmp[0], indices[-1]+1\n",
    "                d[tmp[0]] = tmp[1]\n",
    "            low = min(low, nums[p2])\n",
    "            high = max(high, nums[p2])\n",
    "            output = max(output, p2-p1+1)\n",
    "            p2 += 1\n",
    "        return output\n",
    "        \"\"\"\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        # 双指针 i, j，枚举左端点 i, 同时向右移动 j，将 nums[j] 加入最小堆\n",
    "        mx, mn = [], []\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            while mn and mn[0][-1] < i:\n",
    "                heappop(mn)\n",
    "            while mx and mx[0][-1] < i:\n",
    "                heappop(mx) \n",
    "            while j < n:\n",
    "                if (mn and abs(nums[j] - mn[0][0]) > limit) or (mx and abs(nums[j] + mx[0][0]) > limit):\n",
    "                    break\n",
    "                heappush(mn, (nums[j], j))\n",
    "                heappush(mx, (-nums[j], j))\n",
    "                j += 1\n",
    "            ans = max(ans, j-i)\n",
    "            if mn and nums[i] == mn[0][0]:\n",
    "                heappop(mn)\n",
    "            if mx and nums[i] == -mx[0][0]:\n",
    "                heappop(mx)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        import heapq\n",
    "        n, p1, p2, h1, h2, output = len(nums), 0, 1, [(nums[0],0)], [(-nums[0],0)], 1\n",
    "        while p2<n:\n",
    "            heapq.heappush(h1, (nums[p2],p2))\n",
    "            heapq.heappush(h2, (-nums[p2],p2))\n",
    "            tmp = heapq.heappop(h1)\n",
    "            while nums[p2]-tmp[0] > limit:\n",
    "                if tmp[1]>=p1:\n",
    "                    p1 = tmp[1]+1\n",
    "                tmp = heapq.heappop(h1)\n",
    "            heapq.heappush(h1, tmp)\n",
    "            tmp = heapq.heappop(h2)\n",
    "            while -tmp[0]-nums[p2] > limit:\n",
    "                if tmp[1]>=p1:\n",
    "                    p1 = tmp[1]+1\n",
    "                tmp = heapq.heappop(h2)\n",
    "            heapq.heappush(h2, tmp)\n",
    "            output = max(output, p2-p1+1)\n",
    "            p2 = p2+1\n",
    "        return output\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        if len(nums) <= 1:\n",
    "            return len(nums)\n",
    "        local_max_window = deque()\n",
    "        local_min_window = deque()\n",
    "        local_min_window.append((0,nums[0]))\n",
    "        local_max_window.append((0,nums[0]))\n",
    "        p_l = 0\n",
    "        p_r = 1\n",
    "        result = 1\n",
    "        l = len(nums)\n",
    "\n",
    "        while p_r < l:\n",
    "            while ((not local_max_window) or (not local_min_window) or (local_max_window and local_min_window and local_max_window[0][1] - local_min_window[0][1] <= limit)) and p_r < l:\n",
    "                num_r = nums[p_r]\n",
    "                while local_max_window and local_max_window[-1][1] < num_r:\n",
    "                    local_max_window.pop()\n",
    "                local_max_window.append((p_r,num_r))\n",
    "                while local_min_window and local_min_window[-1][1] > num_r:\n",
    "                    local_min_window.pop()\n",
    "                local_min_window.append((p_r,num_r))\n",
    "                p_r += 1\n",
    "                if local_max_window[0][1] - local_min_window[0][1] <= limit:\n",
    "                    result = max(result, p_r - p_l)\n",
    "\n",
    "            while local_min_window and local_max_window and local_max_window[0][1] - local_min_window[0][1] > limit:\n",
    "                if local_max_window[0][0] == p_l:\n",
    "                    local_max_window.popleft()\n",
    "                if local_min_window[0][0] == p_l:\n",
    "                    local_min_window.popleft()\n",
    "                p_l += 1\n",
    "                result = max(result, p_r - p_l ) \n",
    "            print(p_l, p_r, local_max_window, local_min_window, result)\n",
    "            print()\n",
    "        \n",
    "        \n",
    "        return result\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        left = right = 0\n",
    "        delay_small = defaultdict(int)\n",
    "        delay_large = defaultdict(int)\n",
    "        smalls = []\n",
    "        larges = []\n",
    "\n",
    "        while right < len(nums):\n",
    "            n = nums[right]\n",
    "            heappush(smalls, n)\n",
    "            heappush(larges, -n)\n",
    "            \n",
    "            while len(smalls) > 0 and delay_small[smalls[0]] > 0:\n",
    "                delay_small[smalls[0]] -= 1\n",
    "                heappop(smalls)\n",
    "\n",
    "            while len(larges) > 0 and delay_large[-larges[0]] > 0:\n",
    "                delay_large[-larges[0]] -= 1\n",
    "                heappop(larges)\n",
    "            \n",
    "            largest = -larges[0]\n",
    "            smallest = smalls[0]\n",
    "\n",
    "            if largest - smallest > limit:\n",
    "                n = nums[left]\n",
    "                delay_small[n] += 1\n",
    "                delay_large[n] += 1\n",
    "                left += 1\n",
    "            \n",
    "            right += 1\n",
    "        \n",
    "        return right - left\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        left = right = 0\n",
    "        delay_small = defaultdict(int)\n",
    "        delay_large = defaultdict(int)\n",
    "        smalls = []\n",
    "        larges = []\n",
    "\n",
    "        while right < len(nums):\n",
    "            n = nums[right]\n",
    "            heappush(smalls, n)\n",
    "            heappush(larges, -n)\n",
    "            \n",
    "            while len(smalls) > 0 and delay_small[smalls[0]] > 0:\n",
    "                delay_small[smalls[0]] -= 1\n",
    "                heappop(smalls)\n",
    "\n",
    "            while len(larges) > 0 and delay_large[-larges[0]] > 0:\n",
    "                delay_large[-larges[0]] -= 1\n",
    "                heappop(larges)\n",
    "            \n",
    "            largest = -larges[0]\n",
    "            smallest = smalls[0]\n",
    "\n",
    "            if largest - smallest > limit:\n",
    "                n = nums[left]\n",
    "                delay_small[n] += 1\n",
    "                delay_large[n] += 1\n",
    "                left += 1\n",
    "            \n",
    "            right += 1\n",
    "        \n",
    "        return right - left\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubarray(self, nums: List[int], limit: int) -> int:\n",
    "        n = len(nums)\n",
    "        stack_max, stack_min = deque(), deque()\n",
    "        ret = 0\n",
    "\n",
    "        l, r = 0, 0\n",
    "        while r < n:\n",
    "            num = nums[r]\n",
    "            while stack_max and stack_max[-1][0] < num:\n",
    "                stack_max.pop()\n",
    "            while stack_min and stack_min[-1][0] > num:\n",
    "                stack_min.pop()\n",
    "            \n",
    "            stack_max.append((num, r))\n",
    "            stack_min.append((num, r))\n",
    "            while stack_max[0][0] - stack_min[0][0] > limit:\n",
    "                if stack_max[0][1] < stack_min[0][1]:\n",
    "                    l = stack_max[0][1] + 1\n",
    "                    stack_max.popleft()\n",
    "                else:\n",
    "                    l = stack_min[0][1] + 1\n",
    "                    stack_min.popleft()\n",
    "            \n",
    "            ret = max(ret, r - l + 1)\n",
    "            r += 1\n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
